package com.hy.study.practice.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找 数据必须是有序的
 */
public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1, 2, 2, 3, 3, 4, 5, 6, 7};
        System.out.println(binarySearch(arr, 4, 0, arr.length - 1));
        ArrayList<Integer> indexs = new ArrayList<>();
        binarySearch(arr, 3, 0, arr.length - 1, indexs);
        System.out.println(indexs);

    }

    /**
     * 二分查找 递归
     *
     * @param arr   待查询的数组
     * @param value 带查询的数
     * @param left  左边起的索引
     * @param right 右边起的索引
     * @return 找到的下标ID
     */
    private static int binarySearch(int[] arr, int value, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midValue = arr[mid];
        if (value > midValue) {
            //向右递归
            return binarySearch(arr, value, mid + 1, right);
        } else if (value < midValue) {
            //向左递归
            return binarySearch(arr, value, left, mid - 1);
        } else {
            //找到了
            return mid;
        }
    }

    /**
     * 二分查找 递归
     *
     * @param arr    待查询的数组
     * @param value  带查询的数
     * @param left   左边起的索引
     * @param right  右边起的索引
     * @param result 多个相同的结果集
     * @return 找到的下标ID
     */
    private static void binarySearch(int arr[], int value, int left, int right, List<Integer> result) {
        if (left > right) {
            return;
        }
        int mid = (left + right) / 2;
        int midValue = arr[mid];
        if (value > midValue) {
            binarySearch(arr, value, mid + 1, right, result);
        } else if (value < midValue) {
            binarySearch(arr, value, left, mid - 1, result);
        } else {
            result.add(mid);
            //这时候需要向左和向右分别查找相同的数据，将相同的下标放在result 中
            int index = mid + 1;
            while (index < arr.length && arr[index] == value) {//向右
                result.add(index);
                index++;
            }
            index = mid - 1;
            while (index > 0 && arr[index] == value) {//向左
                result.add(index);
                index--;
            }

        }
    }

}
